﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0074_Solve : IAlgorithm
    {
        // 130. 被围绕的区域

        // 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

        // 提示：
        //  m == board.length
        //  n == board[i].length
        //  1 <= m, n <= 200
        //  board[i][j] 为 'X' 或 'O'

        public void Test()
        {
            // 算法参数定义
            var board = new char[][] {
            new char[]{'X','X','X','X' },
            new char[]{'X','O','O','X' },
            new char[]{'X','X','O','X' },
            new char[]{'X','O','X','X' }
            };
            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            Solve(board);
            foreach (var item in board)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public void Solve(char[][] board)
        {
            var m = board.Length;
            var n = board[0].Length;
            var direction = new int[][] { new int[] { 0, -1 }, new int[] { 1, 0 }, new int[] { 0, 1 }, new int[] { -1, 0 } };
            var vis = new bool[m, n];
            var stack = new Stack<int[]>();
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (vis[i, j])
                        continue;
                    if (board[i][j] == 'X')
                        continue;
                    stack.Push(new int[] { i, j });
                    var hisList = new List<int[]> { new int[] { i, j } };
                    var faceWall = false;
                    while (stack.Count > 0)
                    {
                        var oldPoint = stack.Pop();
                        vis[oldPoint[0], oldPoint[1]] = true;
                        for (int k = 0; k < direction.Length; k++)
                        {
                            var newX = oldPoint[1] + direction[k][0];
                            var newY = oldPoint[0] + direction[k][1];
                            if (newX < 0 || newX == n || newY < 0 || newY == m)
                                faceWall = true;
                            else if (!vis[newY, newX] && board[newY][newX] == 'O')
                            {
                                stack.Push(new int[] { newY, newX });
                                hisList.Add(new int[] { newY, newX });
                            }
                        }
                    }
                    if (!faceWall)
                        for (int k = 0; k < hisList.Count; k++)
                            board[hisList[k][0]][hisList[k][1]] = 'X';
                }
            }
        }
        
        // 可以先找边上的O,再DFS或BFS,并替换值为其他（如A），全局遍历O改为X,A改为O
    }
}
